#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../include/bst.h"

//inserting a file descriptor into the tree

node* insert_bstnode (node* tree_node, struct file_descriptor *fileDescriptor){
   
  node* temp = NULL;
  int diff;
  
  if(tree_node==NULL){
    tree_node = (node*) malloc(sizeof(node));
    tree_node->fdes = fileDescriptor;
    tree_node->left = NULL;
    tree_node->right = NULL;
  }

  else{
    temp = tree_node;
    diff = strcmp(fileDescriptor->path, (temp->fdes)->path);
    if(diff<0)
      temp->left = insert_bstnode(temp->left, fileDescriptor);
    else if(diff>0)
      temp->right = insert_bstnode(temp->right, fileDescriptor);
   /*else if(diff==0)
     return;*/
        
  }

  return tree_node;

}

//Initialize bst root
void initialize_bst_root(fd *fd1){
    bst_root=(node *)malloc(sizeof(node));
    bst_root->fdes=fd1;
    bst_root->left=NULL;
    bst_root->right=NULL;
}

//deleting a file descriptor from the tree
node* delete_bstnode(node* tree_root, char pathname[]){
  
   node* temp = tree_root;
   node* del_node, * parent_node;
   int diff;

   
   
   diff = strcmp(pathname, (tree_root->fdes)->path);

   while(temp!=NULL && diff!=0){
    parent_node = temp;
    if(diff<0)
      temp = temp->left;
    else
      temp = temp->right;
    diff = strcmp(pathname, (temp->fdes)->path);
  }
 
   if(temp!=NULL)
    { //temp points to the node containing the file descriptor to be deleted

     del_node = temp;

     if(del_node==tree_root) { //node to be deleted is the root 
  
         if(del_node->left==NULL && del_node->right==NULL){ //root has no children
              free(del_node);
              return NULL;
         }

         else if(del_node->left!=NULL && del_node->right==NULL)  //root has a left child only
            tree_root = tree_root->left;

         else if(del_node->left==NULL && del_node->right!=NULL)  //root has a right child only
            tree_root = tree_root->right;

         else{ //root has 2 children
            node* prev = tree_root;
            temp = temp->right;
            while(temp->left!=NULL){ //finding the node to replace the root
             prev = temp;
             temp = temp->left;
            }
            
            temp->left = tree_root->left;
            if(prev!=del_node){
             prev->left = temp->right;
             temp->right = tree_root->right;
            }
            tree_root = temp;

          }
   
     }

     else if(del_node==parent_node->left){ //node to be deleted is a left child
        
        if(del_node->left==NULL && del_node->right==NULL)  //node to be deleted has no children
            parent_node->left = NULL;
        
        else if(del_node->left!=NULL && del_node->right==NULL) //node to be deleted has a left child only
            parent_node->left = del_node->left;
        
        else if(del_node->left==NULL && del_node->right!=NULL)  //node to be deleted has a right child only
            parent_node->left = del_node->right;

        else{ //node to be deleted has 2 children
            node* prev = del_node;
            temp = temp->right;
            while(temp->left!=NULL){ //finding the node to replace the node to be deleted
             prev = temp;
             temp = temp->left;
            }
            parent_node->left = temp; 
            temp->left = del_node->left;
            if(prev!=del_node){
             prev->left = temp->right;
             temp->right = del_node->right;
            }

          }
 
     }

     else{   //node to be deleted is a right child

       if(del_node->left==NULL && del_node->right==NULL)  //node to be deleted has no children
            parent_node->right = NULL;

       else if(del_node->left!=NULL && del_node->right==NULL) //node to be deleted has a left child only
            parent_node->right= del_node->left;

       else if(del_node->left==NULL && del_node->right!=NULL)  //node to be deleted has a right child only
            parent_node->right = del_node->right;
       
       else{ //node to be deleted has 2 children
            node* prev = del_node;
            temp = temp->right;
            while(temp->left!=NULL){ //finding the node to replace the node to be deleted
             prev = temp;
             temp = temp->left;
            }
            parent_node->right = temp; 
            temp->left = del_node->left;
            if(prev!=del_node){
             prev->left = temp->right;
             temp->right = del_node->right;
            }

         } 

     }    
    
     free(del_node); //deleting the node
  }
     return tree_root;

}


//displaying the file descriptors in the tree

void display_bst(node* tree_node){
  
  node* temp = tree_node;
  
  while(temp!=NULL) {

      display_bst(temp->left);
      printf("\nFile name: %s", (temp->fdes)->filename);
      printf("\nAbsolute path: %s", (temp->fdes)->path);
      printf("\nFile type: %s", (temp->fdes)->filetype);
      printf("\nFile size: %d", (temp->fdes)->filesize);
      printf("\nBlock number: %d", (temp->fdes)->blockno);
      printf("\n");
      display_bst(temp->right);
      return;

   }
}

//searching for a file in the tree

int search_bstnode (node* tree_node, char filepath[]){

   node* temp = tree_node;
   int diff;

   if(temp==NULL){

     //printf("Element not found!!\n");
     return -100;  //-100 because -1 is the block no. for directory

   }

   else {
      
      diff = strcmp(filepath, (temp->fdes)->path);

      if(diff==0)
       //printf("Element found!\n");
       return (temp->fdes)->blockno;
   
      else if(diff<0)
        return search_bstnode(temp->left, filepath);

      else 
        return search_bstnode(temp->right, filepath);
 
    }

}

 
